/**

   btree.c
   =======
	
	
**/


/**

   Includes
   --------
	
   - stdlib.h   : malloc, free
   - stdint.h   : standard type (uint8_t ...)
   - stdio.h    : printf
   - pthread.h  : pthread
   - bitfield.h : bitfield
   - debug.h    : debug helpers
   - btree.h    : self header

**/

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <pthread.h>
#include <bitfield.h>
#include <debug.h>
#include "btree.h"




/**

   Function: struct b_node* btree_create_node(void)
   -------------------------------------------
	
   Create a b-node
	
**/

struct b_node* btree_create_node(void)
{
  struct b_node* node;
  uint8_t i;
	
  /* Allocation */
  node = (struct b_node*)malloc(sizeof(struct b_node));
  if (node == NULL)
    {
      return NULL;
    }
	
  /* Set up */
  node->is_leaf = 1;
  node->nkeys = 0;

  for(i=0;i<2*BTREE_DEGREE-1;i++)
    {
      node->keys[i] = NULL;
    }	
	
  for(i=0;i<2*BTREE_DEGREE;i++)
    {
      node->children[i] = NULL;
    }
	
  return node;
}



/**

   Function: struct b_tree* btree_create(int (*compare)(struct file*,struct file*))
   ----------------------------------------------------------------------------------------
	
   Create a b-tree
	
**/

struct b_tree* btree_create(int (*compare)(struct file*,struct file*))
{
  struct b_tree* t;
  struct b_node* node;

  /* Allocate tree */
  t = (struct b_tree*)malloc(sizeof(struct b_tree));
  if (t == NULL)
    {
      return NULL;
    }

  /* Allocate a node */
  node = btree_create_node();
  if (node == NULL)
    {
      free(t);
      return NULL;
    }

  /* Set node as root tree */
  t->root = node;

  /* Set compare function */
  t->compare = compare;

  /* Initialize lock */
  pthread_mutex_init(&(t->lock),NULL);

  /* return tree */
  return t;

}


/**

   Function: void btree_delete_node(struct b_node* node)
   -----------------------------------------------------
	
   Delete a b-node
	
**/

void btree_delete_node(struct b_node* node)
{
  if (node != NULL)
    {
      int i;
      for(i=0;i<node->nkeys;i++)
	{
	  file_delete(node->keys[i]);
	}
      free(node);
    }

  return;
}


/**

   Function: void btree_delete_nodes(struct b_node* node)
   ------------------------------------------------------

   Recursively delete a b_node and its children

**/

void btree_delete_nodes(struct b_node* node)
{
  if (node == NULL)
    {
      return;
    }
  else
    {
      int i;

      /* Delete children */
      for(i=0;i<2*BTREE_DEGREE;i++)
	{
	  btree_delete_nodes(node->children[i]);
	}

      /* Delete node */
      btree_delete_node(node);

    }

}


/**

   Function: void btree_delete(struct b_tree* t)
   ---------------------------------------------
	
   Delete a b-tree
	
**/

void btree_delete(struct b_tree* t)
{
  btree_delete_nodes(t->root);
  free(t);
  return;
}


/**

   Function: struct b_node* btree_split(struct b_node* node_x, uint8_t i, struct b_node* node_y)
   ---------------------------------------------------------------------------------------------
	
   node_x is a non full internal node, i an index and node_y=node_x->children[i] is full.
   Split node_y into a new node.

**/

static struct b_node* btree_split(struct b_node* node_x, uint8_t i, struct b_node* node_y)
{
  struct b_node* node_z;
  uint8_t j;
	
  /* Allocate new node */
  node_z = btree_create_node();
  if (node_z == NULL)
    {
      return NULL;
    }
	
  /* Set up */
  node_z->is_leaf = node_y->is_leaf;
  node_z->nkeys = BTREE_DEGREE - 1;
	
  /* Copy second half node_y keys. node_y is full (2*BTREE_DEGREE - 1 keys) so we copy BTREE_DEGREE - 1 keys */
  for(j=0;j<BTREE_DEGREE - 1;j++)
    {
      node_z->keys[j] = node_y->keys[j+BTREE_DEGREE];
    }

  /* Copy second half children if node_y is an internal node */
  if (!(node_y->is_leaf))
    {
      /* node_y is full, so it has 2*BTREE_DEGREE children. We thus copy BTREE_DEGREE children in node_z */
      for(j=0;j<BTREE_DEGREE;j++)
	{
	  node_z->children[j] = node_y->children[j+BTREE_DEGREE];
	  node_y->children[j+BTREE_DEGREE] = NULL;
	}
    }

  /* Update node_y count */
  node_y->nkeys -= BTREE_DEGREE ;
	
  /* Shift node_x children to make room for node_z */
  for(j=node_x->nkeys;j>i;j--)
    {
      node_x->children[j+1] = node_x->children[j];
    }
  /* Attach node_z */
  node_x->children[i+1] = node_z;
	
  /* Shift node_x keys to make room for node_y median key */
  if (node_x->nkeys)
    {
      for(j=node_x->nkeys-1;(j>=i)&&(j!=UINT8_MAX);j--)
	{
	  node_x->keys[j+1] = node_x->keys[j];
	}
    }
	
  /* Insert node_y median key */
  node_x->keys[i] = node_y->keys[BTREE_DEGREE-1];
	
  /* Update node_x count */
  node_x->nkeys++;
	
  return node_z;

}



/**

   Function: void btree_insert_nonfull(struct b_tree* t, b_node* node_x, struct file* k)
   -----------------------------------------------------------------------------------------
	
   Insert key k into nonfull tree node_x
	
**/

static void btree_insert_nonfull(struct b_tree* t, struct b_node* node_x, struct file* k)
{
  uint8_t i;

  /* Last key index */
  i = node_x->nkeys-1;
	
  /* If node_x is a leaf, insert k in keys (node_x is necessarily non full) */
  if (node_x->is_leaf)
    {
      /* Shift keys to make room for k */
      if (node_x->nkeys)
	{
	  while( (i!=UINT8_MAX) &&  (t->compare(node_x->keys[i],k) > 0) )
	    {
	      node_x->keys[i+1] = node_x->keys[i];
	      i--;
	    }
			
	}
      /* Insert k */
      node_x->keys[(uint8_t)(i+1)] = k;
		
      /* Update count */
      node_x->nkeys++;
    }
  else
    {
      /* Find  matching child index to insert into */
      while( (i!=UINT8_MAX) && (t->compare(node_x->keys[i],k) > 0) )
	{
	  i--;
	}
      i++;
		
      /* split child into 2 new children if full */
      if (node_x->children[i]->nkeys == 2*BTREE_DEGREE-1)
	{
	  if (btree_split(node_x,i,node_x->children[i]) == NULL)
	    {
	      return;
	    }
			
	  /* Determine which of the 2 children is the one to descend */
	  if (t->compare(k,node_x->keys[i]) > 0)
	    {
	      i++;
	    }
	}
		
		
      /* Recurse insert */
      btree_insert_nonfull(t,node_x->children[i],k);
    }
	
  return;
}


/**

   Function: struct b_node* btree_insert(b_node* t, struct file* k)
   --------------------------------------------------------------------
	
   Insert key k into tree t
	
**/

int btree_insert(struct b_tree* t, struct file* k)
{

  if (t->root->nkeys == (2*BTREE_DEGREE-1))
    {
      struct b_node* s;
	
      /* Allocate new parent for this full node */
      s = btree_create_node();
      if (s == NULL)
	{
	  return EXIT_FAILURE;
	}
		
      /* Set up */
      s->is_leaf = 0;
      s->nkeys = 0;
      s->children[0] = t->root;

      /* Split full node */
      if (btree_split(s,0,t->root) == NULL)
	{
	  btree_delete_node(s);
	  return EXIT_FAILURE;
	}
		
      /* Insert in a non full tree */
      btree_insert_nonfull(t,s,k);
		
      /* Set new root */
      t->root = s;

      return EXIT_SUCCESS;

    }
  else
    {
      /* Effective insert */
      btree_insert_nonfull(t,t->root,k);
      return EXIT_SUCCESS;
    }
	
}


/**

   Function: struct file* btree_search_node(struct b_tree* b, struct b_node* t, struct file* k)
   --------------------------------------------------------------------------------------------
	
   Find k in tree rooted at node t and return struct b_search
	
**/
	
struct file* btree_search_node(struct b_tree* b, struct b_node* t, struct file* k)
{
  uint8_t i;
	
  /* Search for k in node */
  i=0;
  while( (i < t->nkeys) &&  (b->compare(k,t->keys[i]) > 0) )
    {
      i++;
    }
	
  /* Return if found */
  if ( (i < t->nkeys)&&(b->compare(k,t->keys[i])==0 ) )
    {
      return t->keys[i];
    }
  /* If not found, return NULL is t is leaf, recurse  on children[i] otherwise */
  else if (t->is_leaf)
    {
      return NULL;
    }
  else
    {
      return btree_search_node(b,t->children[i],k);
    }

}


/**

   Function: struct file* btree_search(struct b_tree* t, struct file* k)
   ---------------------------------------------------------------------
	
   Find k in tree t and return struct b_search
	
**/
	
struct file* btree_search(struct b_tree* t, struct file* k)
{
  return btree_search_node(t,t->root,k);
}


/**

   Function: struct file* btree_predecessor(struct b_node* node_x)
   -------------------------------------------------------------------

   Return predecessor key of k in node_x.
   Always branch right in tree

**/

static struct file* btree_predecessor(struct b_node* node_x)
{
  if (node_x->children[node_x->nkeys] == NULL)
    {
      return node_x->keys[node_x->nkeys-1];
    }

  return btree_predecessor(node_x->children[node_x->nkeys]);

}


/**

   Function: struct file* btree_successor(struct b_node* node_x)
   -----------------------------------------------------------------

   Return successor key of k in node_x
   Alway branch left

**/

static struct file* btree_successor(struct b_node* node_x)
{
  if (node_x->children[0] == NULL)
    {
      return node_x->keys[0];
    }

  
  return btree_successor(node_x->children[0]);  
}


/**

   Function: void btree_remove_key(struct b_tree* t,struct b_node* node_x, struct file* k)
   -------------------------------------------------------------------------------------------
	
   Delete key k in tree node_x
	
**/

static void btree_remove_key(struct b_tree* t,struct b_node* node_x, struct file* k)
{
  uint8_t i,j;
	
  /* Find i such as node_x[i] <= k */
  i=0;
  while( (i<node_x->nkeys) && (t->compare(k,node_x->keys[i]) > 0) )
    {
      i++;
    }

	
  /* k found and node_x is leaf (case 1) */
  if ( (i<node_x->nkeys) && (t->compare(k,node_x->keys[i])==0) && (node_x->is_leaf) )
    {
      /* Shift left keys to delete node_x->keys[i] */
      while( i < node_x->nkeys-1 )
	{
	  node_x->keys[i] = node_x->keys[i+1];
	  i++;
			
	}
  
      /* Update nkeys */
      node_x->nkeys--;

      return;
    }
	
  /* k found and node_x is not a leaf (case 2) */
  if ( (i<node_x->nkeys) && (t->compare(k,node_x->keys[i])==0) )
    {
      struct b_node* node_y;
      struct b_node* node_z;
      struct file* kprim;
		
      /* Get preceding child */
      node_y = node_x->children[i];
		
      /* case 2a */
		
      if (node_y->nkeys >= BTREE_DEGREE)
	{

	  /* Get preceding key in child */
	  kprim = btree_predecessor(node_y);
	  /* Delete kprim in node_y subtree */
	  btree_remove_key(t,node_y,kprim);
	  /* Replace k with kprim in node_x */
	  node_x->keys[i] = kprim;
			
	  return;
	}
		
      /* Get succeding child */
      node_z = node_x->children[i+1];
		
      /* case 2b */
      if (node_z->nkeys >= BTREE_DEGREE)
	{

	  /* Get preceding key in child */
	  kprim =  btree_successor(node_z);
	  /* Delete kprim in node_y subtree */
	  btree_remove_key(t,node_z,kprim);
	  /* Replace k with kprim in node_x */
	  node_x->keys[i] = kprim;
			
	  return;
	}
		
      /* case 2c */

      /* Merge k in node_y */
      node_y->keys[BTREE_DEGREE-1] = node_x->keys[i];
      /* Shift left remaining keys and children in node_x */
      for(j=i;j<node_x->nkeys;j++)
	{
	  node_x->keys[j] = node_x->keys[j+1];
	  node_x->children[j+1] = node_x->children[j+2];
	  node_x->children[j+2] = NULL;
	}
      /* Update nkeys */
      node_x->nkeys--;
		
      /* Merge node_y with node_z */
      for(j=BTREE_DEGREE;j<2*BTREE_DEGREE-1;j++)
	{
	  node_y->keys[j] = node_z->keys[j-BTREE_DEGREE];
	  node_y->children[j] = node_z->children[j-BTREE_DEGREE];
	}
      node_y->children[2*BTREE_DEGREE-1] = node_z->children[BTREE_DEGREE-1];
      /* Update nkeys */
      node_y->nkeys = 2*BTREE_DEGREE-1;
      /* Release node_z */
      btree_delete_node(node_z);
		
      /* Delete k in node_y */
      btree_remove_key(t,node_y,k);
		
      return;
    }

  /* k not found and node_x is an internal node (case 3) */
  if (!(node_x->is_leaf))
    {
      struct b_node* node_s;
      struct b_node* node_z;
		
      /* Get child that must contain k */
      node_s = node_x->children[i];
	
      if (node_s->nkeys == BTREE_DEGREE-1)
	{
	  /* Left sibling (case 3a) */
	  if ( (i) && (node_x->children[i-1]->nkeys > BTREE_DEGREE-1) )
	    {
	      /* Add node_x->keys[i-1] to node_s (and not key[i] which is superior to k !)*/

	      /* Update count */
	      node_s->nkeys++;
				
	      /* Shift right node_s keys and children to make room for node_x->key[i-1] */
	      for(j=node_s->nkeys-1;j>0;j--)
		{
		  node_s->keys[j] = node_s->keys[j-1];
		  node_s->children[j+1] = node_s->children[j];
		}
	      node_s->children[1]=node_s->children[0];
				
	      /* Set node_x->key[i-1] in node_s at index 0*/
	      node_s->keys[0] = node_x->keys[i-1];
	      /* Move left sibling final child into node_s */
	      node_s->children[0] = (node_x->children[i-1])->children[node_x->children[i-1]->nkeys];
				
	      /* Update node_x->keys[i-1] with left sibling final key */
	      node_x->keys[i-1] = (node_x->children[i-1])->keys[node_x->children[i-1]->nkeys-1];

	      /* Clean left sibling child */
	      (node_x->children[i-1])->children[node_x->children[i-1]->nkeys] = NULL;

	      /* Update left sibling nkeys */
	      (node_x->children[i-1])->nkeys--;

	    }
	  /* Right sibling (case 3a) */
	  else if ( (i < node_x->nkeys) && ((node_x->children[i+1])->nkeys > BTREE_DEGREE-1) )
	    {
	      /* Add node_x->keys[i] to node_s */
	      node_s->nkeys++;
	      node_s->keys[BTREE_DEGREE-1] = node_x->keys[i];
				
	      /* Set right sibling child first key in place of key[i] */
	      node_x->keys[i] = (node_x->children[i+1])->keys[0];
	      /* Rattach right sibling first child as node_s last child */
	      node_s->children[BTREE_DEGREE] = (node_x->children[i+1])->children[0];
				
	      /* Shift left right sibling keys and children */
	      for(j=0;j<(node_x->children[i+1])->nkeys;j++)
		{
		  (node_x->children[i+1])->keys[j] = (node_x->children[i+1])->keys[j+1];
		  (node_x->children[i+1])->children[j] = (node_x->children[i+1])->children[j+1];
		  (node_x->children[i+1])->children[j+1] = NULL;
		}
				
	      /* Update right sibling nkeys */
	      (node_x->children[i+1])->nkeys--;
	    }
	  else
	    {
	      /* Case 3b */

	      if (i < node_x->nkeys)
		{
		  /* Move node_x->keys[i] down to its child */
		  node_s->keys[BTREE_DEGREE-1] = node_x->keys[i];
		  /* Get right sibling */
		  node_z=node_x->children[i+1];
		  /* Shift left node_x keys and children */
		  for(j=i;j<node_x->nkeys-1;j++)
		    {
		      node_x->keys[j] = node_x->keys[j+1];
		      node_x->children[j+1] = node_x->children[j+2];
		      node_x->children[j+2] = NULL;
		    }
		  node_x->children[j+1] = NULL;
	

		  /* Update node_x nkeys */
		  node_x->nkeys--;

		  /* Merge node_s and node_z in node_s */
		  for(j=BTREE_DEGREE;j<2*BTREE_DEGREE-1;j++)
		    {
		      node_s->keys[j] = node_z->keys[j-BTREE_DEGREE];
		      node_s->children[j] = node_z->children[j-BTREE_DEGREE];
		    }
		  node_s->children[2*BTREE_DEGREE-1] = node_z->children[BTREE_DEGREE-1];
		  node_s->nkeys = 2*BTREE_DEGREE-1;

		  btree_delete_node(node_z); 

		}
	      else if (i)
		{
		  /* Get left sibling */
		  node_z=node_x->children[i-1];
					
		  /* Move node_x->keys[i-1] down to its child  */
		  node_z->keys[BTREE_DEGREE-1] = node_x->keys[i-1];
					
		  /* Shift left node_x keys and children */
		  for(j=i;j<node_x->nkeys-1;j++)
		    {
		      node_x->keys[j] = node_x->keys[j+1];
		      node_x->children[j] = node_x->children[j+1];
		      node_x->children[j+1] = NULL;
		    }
		  node_x->children[j] = NULL;

		  /* Update node_x nkeys */
		  node_x->nkeys--;
		  /* Merge node_s and node_z in node_z */
		  for(j=BTREE_DEGREE;j<2*BTREE_DEGREE-1;j++)
		    {
		      node_z->keys[j] = node_s->keys[j-BTREE_DEGREE];
		      node_z->children[j] = node_s->children[j-BTREE_DEGREE];
		    }
		  node_z->children[2*BTREE_DEGREE-1] = node_s->children[BTREE_DEGREE-1];
		  node_z->nkeys = 2*BTREE_DEGREE-1;
		  			
		  btree_delete_node(node_s);
		  /* Recurse is on node_s :) */
		  node_s = node_z;
		}
					
	    }

	}
    
      btree_remove_key(t,node_s,k);
      
    }
	
  return;
}


/**

   Function: struct b_node* btree_remove(struct b_node* t, struct file* k)
   ---------------------------------------------------------------------------
	
   Remove k from t
	
**/

int btree_remove(struct b_tree* t, struct file* k)
{
  struct b_node* node;

  /* Remove key */
  btree_remove_key(t,t->root,k);

  /* Remove root if empty */
  while ( (t->root->nkeys == 0) && (!(t->root->is_leaf)) )
    {
      node=t->root->children[0];
      btree_delete_node(t->root);
      t->root = node;
    }
	
  return EXIT_SUCCESS;
}
